package alo.p6.work;

import org.junit.Test;
import alo.p6.BinaryTreeNode;

import java.util.LinkedList;
import java.util.Queue;

//二叉树满结点的个数
public class NumberOfFullNodesInBinaryTree {
    @Test
    public void test(){
        int[] A={1,2,4,5,3,6,7};
        int[] B={4,2,5,1,6,3,7};
        BuildBinaryTree buildBinaryTree=new BuildBinaryTree();
        BinaryTreeNode root = buildBinaryTree.buildBinaryTree(B,A,0,6);
        System.out.println(numberOfFullNodesInBinaryTree(root));//3
        System.out.println(numberOfFullNodesInBinaryTree2(root));//1
    }
    //非递归
    int numberOfFullNodesInBinaryTree(BinaryTreeNode root){
        BinaryTreeNode temp;
        Queue<BinaryTreeNode> queue=new LinkedList<>();
        int count=0;
        if (root==null) return 0;
        queue.offer(root);
        while (!queue.isEmpty()){
            temp=queue.poll();
            if (temp.getLeft()!=null&&temp.getRight()!=null)
                count++;
            if (temp.getLeft()!=null) queue.offer(temp.getLeft());
            if (temp.getRight()!=null) queue.offer(temp.getRight());
        }
        return count;
    }
    //递归的方式是不可行的，因为递归的基本形式对于第一个就成立，不是对子树适用的
    int numberOfFullNodesInBinaryTree2(BinaryTreeNode root){
        if (root==null) return 0;
        if (root.getLeft()!=null&&root.getRight()!=null) return 1;
        int left,right;
        left=numberOfFullNodesInBinaryTree2(root.getLeft());
        right=numberOfFullNodesInBinaryTree2(root.getRight());
        return left+right;
    }
}
